import java.util.Stack;

/**
 * 最小栈:O(1)的时间复杂度求出栈中的最小值
 */
class MinStack {

    Stack<Integer> stack;       //普通的栈
    Stack<Integer> minStack;    //存储相应的较小值的栈

    public MinStack() {
        stack = new Stack<>();
        minStack = new Stack<>();
    }

    //入栈
    public void push(int val) {
        stack.push(val);    //入栈
        if(minStack.empty() || minStack.peek() > val) {
                    //为空 或者 即将入栈stack的数据(val)小于等于栈minStack的栈顶数据时，
                    //将 val 入到栈minStack 中
            minStack.push(val);
        }
    }

    //出栈
    public void pop() {
        if(stack.empty()) {
            return;
        }
        if(stack.peek().equals(minStack.peek())) {
            //出栈stack的数据等于栈minStack的栈顶数据时，minStack的栈顶数据也要出栈
            minStack.pop();
        }
        stack.pop();
    }
    
    public int top() {
        return stack.peek();
    }
    
    public int getMin() {
        if(minStack.empty()) {
            return 0;   //为空返回0 根据测试用例确定
        }
        return minStack.peek();
    }
}
